#include <iostream>
#include <vector>
using namespace std;

const int DIRECTION[4][2] ={{-1,0},{1,0},{0,-1},{0,1}}; 

class Maze
{
    public:
        Maze(const vector<vector<char>> maze)
        {
            _maze = maze;
            _isvisited.resize(_maze.size(),vector<bool> _maze[0].size(),false);
            _row = maze.size();
            _col = maze[0].size();
        }

        bool isValid(int x,int y)
        {
            return (x >= 0 && x < row && y >= 0 && y < col && _is_visited[x][y] != true);
        }

        bool backtrace(int x,int y)
        {
            if(_maze[x][y] == 'E') return true;
            _is_visited[x][y] = true;

            for(int i = 0; i < 4; i++)
            {
                int newX = x + DIRECTION[i][0];
                int newY = y + DIRECTION[i][1];
                if(isValid(newX,newY))
                {
                    if(backtrace(newX,newY)) return true;
                }
            }

            _is_visited[x][y] = false;
            return false;
        }

        bool solver()
        {
            for(int i = 0; i < _maze.size())
            {
                for(int j = 0; j < _maze[0].size())
                {
                    if(_maze[i][j] == 'S')
                    {
                        backtrace(i,j);
                    }
                }
            }
        }
    private:
        vector<vector<char>> _maze;
        vector<vector<bool>> _is_visited;
        int _row;
        int _col;
};

int main()
{

    return 0;
}
